package cn.edu.njust.alg.leetcode;


/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_34_Search_for_a_Range {

	public static int binarySearch(int[] nums, int low, int high, int target) {
		int mid = 0;
		while (low <= high) {
			mid = (low + high) >> 1;
			if (nums[mid] > target) {
				high = mid - 1;
			} else if (nums[mid] < target) {
				low = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	public static int[] searchRange(int[] nums, int target) {
		int begin = -1;
		int end = -1;
		int r = binarySearch(nums, 0, nums.length - 1, target);
		if (r == -1) {
			return new int[] { begin, end };
		} else {
			begin = end = r;
			while ((r = binarySearch(nums, 0, begin - 1, target)) != -1) {
				begin = r;
			}
			while ((r = binarySearch(nums, end + 1, nums.length - 1, target)) != -1) {
				end = r;
			}
		}
		return new int[] { begin, end };
	}

	public static int searchInsert(int[] nums, int target) {
		int mid = 0;
		int low = 0;
		int high = nums.length - 1;
		while (low <= high) {
			mid = (low + high) >> 1;
			if (nums[mid] > target) {
				high = mid - 1;
			} else if (nums[mid] < target) {
				low = mid + 1;
			} else {
				return mid;
			}
		}
		if(high < 0) return 0;
        if(low >= nums.length) return nums.length;
		return low;

	}

	public static void main(String[] args) {

		int[] nums = { 1, 3, 5, 6 };
		int target = 2;
		// System.out.println(binarySearch(nums, 0, nums.length - 1, target));
		// ArrayUtils.printArray(searchRange(nums, target));
		System.out.println(searchInsert(nums, target));
	}

}
